554. Brick Wall
Medium

There is a rectangular brick wall in front of you with n rows of bricks. The ith row has some number of bricks each of the same height (i.e., one unit) but they can be of different widths. The total width of each row is the same.

Draw a vertical line from the top to the bottom and cross the least bricks. If your line goes through the edge of a brick, then the brick is not considered as crossed. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Given the 2D array wall that contains the information about the wall, return the minimum number of crossed bricks after drawing such a vertical line.

 

Example 1:

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2

Example 2:

Input: wall = [[1],[1],[1]]
Output: 3

 

Constraints:

  • n == wall.length
  • 1 <= n <= 104
  • 1 <= wall[i].length <= 104
  • 1 <= sum(wall[i].length) <= 2 * 104
  • sum(wall[i]) is the same for each row i.
  • 1 <= wall[i][j] <= 231 - 1
Accepted
89.5K
Submissions
172.7K
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.80 (30 votes)

Premium

Video Solution


 

Solution Article


Approach #1 Brute Force [Time Limit Exceeded]

In this approach, we consider the given wall as being made up of virtual bricks each of width 1. We traverse over the width of the wall only in terms of these virtual bricks.

Firstly, we need to determine the total number of virtual bricks. For this, we determine the width of the given wall by summing up the widths of the bricks in the first row. This width is stored in sumsum. Thus, we need to traverse over the widthe sumsum times now in terms of 1 unit in each iteration.

We traverse over the virtual bricks in a column by column fashion. For keeping a track of the actual position at which we are currently in any row, we make use of a pospos array. pos[i]pos[i] refers to the index of the brick in the ithi^{th} row, which is being treated as the virtual brick in the current column's traversal. Further, we maintain a countcount variable to keep a track of the number of bricks cut if we draw a line down at the current position.

For every row considered during the column-by-column traversal, we need to check if we've hit an actual brick boundary. This is done by updating the brick's width after the traversal. If we don't hit an actual brick boundary, we need to increment countcount to reflect that drawing a line at this point leads to cutting off 1 more brick. But, if we hit an actual brick boundary, we increment the value of pos[i]pos[i], with ii referring to the current row's index. But, now if we draw a line down through this boundary, we need not increment the countcount.

We repeat the same process for every column of width equal to a virtual brick, and determine the minimum value of countcount obtained from all such traversals.

The following animation makes the process clearer:

Current
1 / 19

Complexity Analysis

  • Time complexity : O(nm)O(n*m). We traverse over the width(nn) of the wall mm times, where mm is the height of the wall.

  • Space complexity : O(m)O(m). pospos array of size mm is used, where mm is the height of the wall.


Approach #2 Better Brute Force[Time LImit Exceeded]

Algorithm

In this approach, instead of traversing over the columns in terms of 1 unit each time, we traverse over the columns in terms of the width of the smallest brick encountered while traversing the current column. Thus, we update pospos array and sumssums appropriately depending on the width of the smallest brick. Rest of the process remains the same as the first approach.

The optimization achieved can be viewed by considering this example:


[[100, 50, 50],
[50, 100],
[150]]

In this case, we directly jump over the columns in terms of widths of 50 units each time, rather than making traversals over widths incrementing by 1 unit each time.

Complexity Analysis

  • Time complexity : O(nm)O(n*m). In worst case, we traverse over the length(nn) of the wall mm times, where mm is the height of the wall.

  • Space complexity : O(m)O(m). pospos array of size mm is used, where mm is the height of the wall.


Approach #3 Using HashMap [Accepted]

Algorithm

In this approach, we make use of a HashMap mapmap which is used to store entries in the form: (sum,count)(sum, count). Here, sumsum refers to the cumulative sum of the bricks' widths encountered in the current row, and countcount refers to the number of times the corresponding sum is obtained. Thus, sumsum in a way, represents the positions of the bricks's boundaries relative to the leftmost boundary.

Let's look at the process first. We traverse over every row of the given wall. For every brick considered, we find the sumsum corresponding to the sum of the bricks' widths encountered so far in the current row. If this sumsum's entry doesn't exist in the mapmap, we create a corresponding entry with an initial countcount of 1. If the sumsum already exists as a key, we increment its corresponding countcount value.

This is done based on the following observation. We will never obtain the same value of sumsum twice while traversing over a particular row. Thus, if the sumsum value is repeated while traversing over the rows, it means some row's brick boundary coincides with some previous row's brick boundary. This fact is accounted for by incrementing the corresponding countcount value.

But, for every row, we consider the sum only upto the second last brick, since the last boundary isn't a valid boundary for the solution.

At the end, we can obtain the maximum countcount value to determine the minimum number of bricks that need to be cut to draw a vetical line through them.

The following animation makes the process clear:

Current
1 / 8
**Complexity Analysis**
  • Time complexity : O(n)O(n). We traverse over the complete bricks only once. nn is the total number of bricks in a wall.

  • Space complexity : O(m)O(m). mapmap will contain atmost mm entries, where mm refers to the width of the wall.

Report Article Issue

Comments: 11
ZebraRabbit's avatar
Read More

We can use a variable to record the maximum count each time when putting keys to the map. Hence we do not need to traverse the map's keySet().

30
Show 1 reply
Reply
Share
Report
rishabhpandita's avatar
Read More

why is last row 2,2 not considered in the animation slides ?

10
Show 1 reply
Reply
Share
Report
coder_xyzzy's avatar
Read More

You do not need two passes.

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> gaps;
        int max_gaps = 0;
        for (const auto& row: wall) {
            int w = 0;
            for (int i = 0; i < row.size() - 1; ++i) {
                w += row[i];
                max_gaps=max(max_gaps, ++gaps[w]);
            }
        }
        return wall.size() - max_gaps;
    }
};

7
Show 1 reply
Reply
Share
Report
gururaj88's avatar
Read More

least bricks simple with itertools

import itertools

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        if not wall:
            return 0
        cumul = [list(itertools.accumulate(line))  for line in wall]
        
        freq = Counter()
        for cumul_line in cumul:
            for brick_sum in cumul_line[:-1]:                
                freq[brick_sum] += 1
        
        if not freq:
            return len(wall)
        most_common_cumul = freq.most_common(1)[0][1]
        return len(wall) - most_common_cumul
     

2
Reply
Share
Report
ismail_durmaz's avatar
Read More

Prefer values method instead of keySet of Map class.

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> count = new HashMap<>();
        
        for(List<Integer> row : wall){
            int current = 0;
            int k = row.size() - 1;
            for(int i = 0; i < k; i++ ){
                current += row.get(i);
                count.put(current, count.getOrDefault(current, 0) + 1);
            }
        }
        
        int max = 0;
        int wallSize = wall.size();
        for(Integer value: count.values()){
            max = Math.max(max, value);
        }
        return wallSize - max;
    }
}

1
Reply
Share
Report
vinod23's avatar
Read More

@yujun you can do that as well.

1
Reply
Share
Report
yujun's avatar
Read More

It's an awesome solution. But may I ask why we traverse from left to right to build "sum" instead of traversing right to left?

1
Show 1 reply
Reply
Share
Report
Ark-kun's avatar
Read More

If wall width >> wall height, the approach #3 is not optimal. We do not need a HashMap with all gap positions. We just need a Heap with the closest gap locations. Then, the space complexity is O(height).

0
Reply
Share
Report
twicetzuyufan's avatar
Read More

When it is said that the time complexity of approach 1 is O(mn), and the time complexity of approach 3 is O(n), aren't they actually the same because in approach 1, mn is the total size of the wall, which in the case where each brick has a width of 1, would be the same as the number of bricks in the wall, which is the n in O(n) for approach 3?

And also for approach 2, what if not all bricks are sizes that are mutliples of the smallest width, then wouldn't we miss some gaps?

0
Reply
Share
Report
jca88's avatar
Read More

Although approach 1 gets TLE, i really really love the idea of the positions array!

0
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
04/23/2021 08:29Accepted40 ms23.5 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.